package 力扣;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 示例 1：

 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
 解释：
 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
 示例 2：
 输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
 输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
 */

public class _406根据身高重建队列 {
    public int[][] reconstructQueue(int[][] people) {
        if(people == null || people.length == 0 || people[0].length == 0) return new int[0][0];

        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if(a[0] == b[0]) return a[1] - b[1]; //升序
                return b[0] - a[0]; //降序
            }
        });
        //获取people的身高数
        int n = people.length;
        //定义一个临时的list
        List<int[]> tmp = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            tmp.add(people[i][1], new int[]{people[i][0], people[i][1]});
        }

        int[][] ret = new int[n][2];
        for(int i = 0; i < n; i++) {
            ret[i][0] = tmp.get(i)[0];
            ret[i][1] = tmp.get(i)[1];
        }
        return ret;
    }
}
